SECDED codes play a pivotal role in data transfer/communication applications. One example is data storage applications. Advances in memory technology have provided the capability of storing increasingly large amounts of data in individual memory packages (or modules). This makes it possible to store/retrieve from a single memory module data that previously was stored/retrieved by accessing multiple modules, providing improvements in performance, power consumption, and scalability. When accessing a single module, it is advantageous to address effectively errors that have a single cause. For example, if several I/O terminals of a module provide respective I/O paths, a failed transmitter driving one of the terminals may be used multiple times per memory access. The bits transferred via any given terminal in a single burst may be considered to be a data symbol. If the terminal transfers data in 4-bit bursts, for example, then the symbol size is four bits. A sixteen-byte transfer might be accomplished by transferring a 4-bit burst (i.e., one symbol) on each of 32 terminals of the memory module. Within knowable limits, a SECDED code that appends four parity check symbols of four bits each is capable of correcting any error in a single data symbol (and detecting errors in two data symbols). Thus, errors repeatedly caused by a single failed transmitter associated with a single terminal may be corrected.
The aforementioned example SECDED code has a Hamming distance of at least four, in terms of symbols. This is a specific example of a linear [n, k, d]q code over a general alphabet GF(q), with n=36 (data+parity check) symbols, k=32 data symbols, code distance d=4, and symbol alphabet size q=16 (24 with 4 bits/symbol), that is, a [36, 32, 4]16 code.
One approach to construct an [n, k, d]q code is a random search of parity check matrices in GF(q). Considering the aforementioned example of a [36, 32, 4]16 code, there are 15×36 different single symbol errors, while the syndrome from the four symbol parity has 65536 possibilities. It thus appears that a random search would likely yield a code. Nevertheless, testing as many as 15×230 H matrices obtained via random search has failed to yield a [36, 32, 4]16 code.
Another approach is to construct a [35, 32, 3]16 code, and extend it with a single parity check to a [36, 32, 4]16 code. Since GCD(35,16)=1, construction of a BCH code with n=35 and d=3 may be considered. BCH codes provide a minimum distance guarantee that is determined by the generator polynomial. However, investigation of BCH codes with n=35 and q=16 reveals that the most efficient BCH codes with d=3 are [35, 31, 3]16 codes, which cannot be extended to a [36, 32, 4]16 code.
Another approach is the use of an existing bound, such as the Gilbert-Varshamov (GV) bound, that indicates feasible codes. However, for the code distance d=4, the GV bound indicates that only k=27.5 is achievable.
Another approach is constructing a [36, 32, 4]16 code as four simultaneous [36, 32, 4]2 codes, or two simultaneous [36, 32, 4]4 codes. However, a [36, 32, 4]2 code does not exist because it violates the Hamming bound. Although a linear [36, 32, 4]4 code would not violate the Hamming bound, it has been found that [36, 32, 4]4 codes do not exist.
It is desirable in view of the foregoing to provide for the construction of distance d linear codes more efficiently than by random searching.